\contentsline {chapter}{Abstract}{ii}{section*.1}
\contentsline {chapter}{List of Tables}{vii}{chapter*.3}
\contentsline {chapter}{List of Figures}{viii}{chapter*.4}
\contentsline {chapter}{\numberline {1}Introduction}{1}{chapter.5}
\contentsline {section}{\numberline {1.1}Motivation}{2}{section.6}
\contentsline {section}{\numberline {1.2}Contribution of This Thesis}{3}{section.7}
\contentsline {section}{\numberline {1.3}A Motivating Example}{4}{section.12}
\contentsline {section}{\numberline {1.4}Organization of the Thesis}{6}{section.18}
\contentsline {chapter}{\numberline {2}Background}{8}{chapter.19}
\contentsline {section}{\numberline {2.1}Aho Ullman Model}{8}{section.20}
\contentsline {section}{\numberline {2.2}Davidson Fraser Model}{9}{section.22}
\contentsline {section}{\numberline {2.3}GCC's Model}{11}{section.24}
\contentsline {section}{\numberline {2.4}GCC's Back End Organization}{12}{section.26}
\contentsline {subsection}{\numberline {2.4.1}RTL Expression Codes}{13}{subsection.31}
\contentsline {section}{\numberline {2.5}Standard Pattern Names}{15}{section.36}
\contentsline {section}{\numberline {2.6}RTL Templates}{15}{section.37}
\contentsline {subsection}{\numberline {2.6.1}define\_insn Expression}{16}{subsection.39}
\contentsline {subsection}{\numberline {2.6.2}define\_expand Expression}{17}{subsection.46}
\contentsline {subsection}{\numberline {2.6.3}define\_split Expression}{19}{subsection.52}
\contentsline {subsection}{\numberline {2.6.4}define\_insn\_and\_split Expression}{19}{subsection.58}
\contentsline {subsection}{\numberline {2.6.5}define\_peephole Expression}{20}{subsection.60}
\contentsline {subsection}{\numberline {2.6.6}define\_peephole2 Expression}{20}{subsection.61}
\contentsline {chapter}{\numberline {3}Methodology}{22}{chapter.63}
\contentsline {section}{\numberline {3.1}Extracting the Form of an RTL Expression}{22}{section.64}
\contentsline {section}{\numberline {3.2}Output Format}{29}{section.96}
\contentsline {section}{\numberline {3.3}Finding Common Patterns between two machines}{31}{section.97}
\contentsline {section}{\numberline {3.4}Instantiating Patterns with Parameters}{31}{section.98}
\contentsline {section}{\numberline {3.5}Merging Pattern Files}{33}{section.102}
\contentsline {section}{\numberline {3.6}Separating Machine-specific parameters from Templates}{34}{section.103}
\contentsline {section}{\numberline {3.7}Summary}{35}{section.104}
\contentsline {chapter}{\numberline {4}Experimental Results}{36}{chapter.105}
\contentsline {section}{\numberline {4.1}Extracting Patterns From MD Files}{36}{section.111}
\contentsline {section}{\numberline {4.2}Common Patterns Between Machines}{37}{section.113}
\contentsline {subsection}{\numberline {4.2.1}Code\_Iterator Equivalence }{38}{subsection.116}
\contentsline {section}{\numberline {4.3}Implications}{39}{section.117}
\contentsline {chapter}{\numberline {5}Related Work}{40}{chapter.118}
\contentsline {chapter}{\numberline {6}Conclusion and Future Work}{43}{chapter.119}
\contentsline {chapter}{\numberline {A}MDParser User's Manual}{45}{appendix.120}
\contentsline {section}{\numberline {A.1}System Requirements}{45}{section.121}
\contentsline {section}{\numberline {A.2}Installation}{45}{section.122}
\contentsline {section}{\numberline {A.3}Options}{46}{section.123}
\contentsline {subsection}{\numberline {A.3.1}parse}{46}{subsection.133}
\contentsline {section}{\numberline {A.4}Patterns in dot Format}{47}{section.134}
\contentsline {subsection}{\numberline {A.4.1}intersect}{47}{subsection.135}
\contentsline {subsection}{\numberline {A.4.2}split}{48}{subsection.136}
\contentsline {subsection}{\numberline {A.4.3}expand}{48}{subsection.137}
\contentsline {chapter}{\numberline {B}Additional Results}{50}{appendix.138}
\contentsline {chapter}{Bibliography}{52}{table.139}
